package leetbook.array;


import java.util.Random;

/**
 * 设计算法来打乱一个没有重复元素的数组
 */
public class Solution6 {

    int[] nums = null;
    Random rd = new Random();

    public Solution6(int[] nums) {
        this.nums = nums;
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return this.nums;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int[] shuf = this.nums.clone();
        int n = shuf.length;
        for (int i = 0; i < n; i++) {
            //每次从[i,n-1]中抽取下标，然后把抽到的数与下标为i的数交换
            int rdIdx = rd.nextInt(n-i)+i; //[0,n-i)+i = [i,n)
            //抽到了，交换
            int temp = shuf[rdIdx];
            shuf[rdIdx] = shuf[i];
            shuf[i] = temp;
        }
        return shuf;
    }
}

/**
 * Your Solution375 object will be instantiated and called as such:
 * Solution375 obj = new Solution375(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */
